package leetcode.hot100;

import datastruct.list.ListNode;

public class Solution19 {

    public ListNode removeNthFromEnd(ListNode head, int n) {
        //可能head被删，引入虚拟头方便操作
        ListNode virNode = new ListNode();
        virNode.next = head;
        //快慢指针，pre指向slow的上一个节点
        ListNode fast = head, slow = head, pre = virNode;
        //fast先走n步
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        //fast和slow同时走，直到fast==null，此时slow所指就是要删的节点
        while (fast!=null){
            fast = fast.next;
            slow = slow.next;
            pre = pre.next;
        }
        //删除slow
        pre.next = slow.next;
        return virNode.next;
    }
}
